package graph.undirectedgraph.algraph;

import graph.inter.UndirectedGraph;
import graph.undirectedgraph.Edge;
import stackandqueue.queue.inter.Queue;
import stackandqueue.queue.linkedqueue.LinkedQueue;

import java.util.Scanner;

/**
 * 无向图 -- 邻接表
 */
public class AdjacencyListGraph implements UndirectedGraph {
    // 顶点数组
    private VexNode[] vexs;
    // 顶点数
    private int numVertexes;
    // 边数
    private int numEdges;

    private boolean[] visited;

    private Scanner sc;

    public AdjacencyListGraph() {
    }

    public AdjacencyListGraph(String[] vexs, int[][] arc) {
        this.vexs = new VexNode[vexs.length];
        this.visited = new boolean[vexs.length];
        for (int i = 0; i < vexs.length; i++) {
            this.vexs[i] = new VexNode(vexs[i]);
        }

        for (int i = 0; i < arc.length; i++) {
            for (int j = 0; j < arc[i].length; j++) {
                if (arc[i][j] > 0 && arc[i][j] < Integer.MAX_VALUE) {
                    EdgeNode temp = new EdgeNode(j, arc[i][j], this.vexs[i].getFirstEdge());
                    this.vexs[i].setFirstEdge(temp);
                    this.numEdges++;
                }
            }
        }
        this.numVertexes = this.vexs.length;
        this.numEdges /= 2;
    }

    @Override
    public void createGraph() {
        System.out.println("输入图的顶点数：");
        numVertexes = sc.nextInt();
        visited = new boolean[numVertexes];
        vexs = new VexNode[numVertexes];
        System.out.println("输入图的边数");
        numEdges = sc.nextInt();
        System.out.println("输入图的顶点：");
        for (int i = 0; i < numVertexes; i++) {
            vexs[i].setData(sc.next());
            vexs[i].setFirstEdge(null);
        }
        for (int i = 0; i < numVertexes; i++) {
            System.out.print(i + "." + vexs[i] + "     ");
        }
        System.out.println();
        for (int k = 0; k < numEdges; k++) {
            System.out.println("输入边（vi,vj）上的下标i,下标j:");
            int i = sc.nextInt();
            int j = sc.nextInt();
            EdgeNode temp0 = new EdgeNode(j, vexs[i].getFirstEdge());
            vexs[i].setFirstEdge(temp0);

            EdgeNode temp1 = new EdgeNode(i, vexs[j].getFirstEdge());
            vexs[j].setFirstEdge(temp1);
        }
    }

    @Override
    public int locateVex(String u) {
        for (int i = 0; i < vexs.length; i++) {
            if (vexs[i].getData().equals(u)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String getVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }
        return vexs[v].getData();
    }

    @Override
    public void putVex(int v, String value) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        vexs[v].setData(value);
    }

    @Override
    public String firstAdjVex(int v) {
        if (v < 0 || v >= vexs.length) {
            return null;
        }
        EdgeNode edgeNode = vexs[v].getFirstEdge();
        return vexs[v].getFirstEdge() == null ? null : vexs[edgeNode.getAdjvexData()].getData();
    }

    @Override
    public String nextAdjVex(int v, int w) {

        return null;
    }

    @Override
    public void insertVex(String v) {
        VexNode[] vexsTemp = new VexNode[vexs.length + 1];
        for (int i = 0; i < vexs.length; i++) {
            vexsTemp[i] = vexs[i];
        }
        vexs = vexsTemp;
        vexs[vexs.length - 1].setData(v);
    }

    @Override
    public void deleteVex(String v) {
        VexNode[] vexsTemp = new VexNode[vexs.length - 1];
        int j = 0;
        for (int i = 0; i < vexs.length; i++) {
            if (!vexs[i].getData().equals(v)) {
                vexsTemp[j++] = vexs[i];
            }
        }
        vexs = vexsTemp;
    }

    @Override
    public void insertArc(int v, int w) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        EdgeNode temp = new EdgeNode(w, vexs[v].getFirstEdge());
        vexs[v].setFirstEdge(temp);
    }

    @Override
    public void deleteArc(int v, int w) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        EdgeNode p = vexs[v].getFirstEdge();
        if (p != null && p.getAdjvexData() == w) {
            vexs[v].setFirstEdge(p.getNext());
        }
        while (p != null) {
            if (p.getNext().getAdjvexData() == w) {
                break;
            }
            p = p.getNext();
        }
        p.setNext(p.getNext().getNext());
    }

    @Override
    public void dfsTraverse(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }

        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
        depthFirstSearch(v);
    }

    @Override
    public void bfsTraverse(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
        Queue<Integer> queue = new LinkedQueue<>();
        queue.enQueue(v);

        while (!queue.queueEmpty()) {
            int temp = queue.deQueue();
            if (!visited[temp]) {
                EdgeNode p = vexs[temp].getFirstEdge();
                while (p != null) {
                    if (!visited[p.getAdjvexData()]) {
                        queue.enQueue(p.getAdjvexData());
                    }
                    p = p.getNext();
                }
                visited[temp] = true;
                System.out.print(vexs[temp].getData() + " ");
            }

        }
    }

    /**
     * 深度优先遍历算法
     *
     * @param v 开始遍历的节点
     */
    private void depthFirstSearch(int v) {
        if (v < 0 || v >= vexs.length) {
            return;
        }

        System.out.print(vexs[v].getData() + " ");
        visited[v] = true;
        EdgeNode p = vexs[v].getFirstEdge();
        while (p != null) {
            if (!visited[p.getAdjvexData()]) {
                depthFirstSearch(p.getAdjvexData());
            }
            p = p.getNext();
        }
    }

    @Override
    public void miniSpanTreePrim() {
        int k, min;
        int[] adjvex = new int[vexs.length]; // 保存相关顶点下标
        int[] lowcost = new int[vexs.length]; // 保存相关顶点间边的权值
        for (int i = 0; i < vexs.length; i++) {
            adjvex[i] = 0;
            lowcost[i] = MA;
        }
        EdgeNode p = vexs[0].getFirstEdge();
        while (p != null) {
            lowcost[p.getAdjvexData()] = p.getWeight();
            p = p.getNext();
        }

        for (int i = 1; i < vexs.length; i++) {
            min = MA;
            k = 0;
            for (int j = 1; j < vexs.length; j++) {
                if (lowcost[j] != 0 && lowcost[j] < min) {
                    min = lowcost[j];
                    k = j;
                }
            }
            System.out.println(adjvex[k] + "-->" + k);
            lowcost[k] = 0;
            EdgeNode point = vexs[k].getFirstEdge();
            while (point != null) {
                if (lowcost[point.getAdjvexData()] != 0
                        && point.getWeight() < lowcost[point.getAdjvexData()]) {
                    lowcost[point.getAdjvexData()] = point.getWeight();
                    adjvex[point.getAdjvexData()] = k;
                }
                point = point.getNext();
            }
        }
    }

    @Override
    public void miniSpanTreeKruskal() {
        // 获取边集数组，并升序排序
        Edge[] edges = getEdges();
        sortEdges(edges);
        // 记录每个节点的终止节点
        int[] parent = new int[numEdges];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = 0;
        }
        //
        int m, n;
        for (int i = 0; i < edges.length; i++) {
            m = find(parent, edges[i].getBegin());
            n = find(parent, edges[i].getEnd());

            if (m != n) {
                parent[m] = n;
                System.out.println(edges[i].getBegin() + "-->" + edges[i].getEnd());
            }
        }
    }

    @Override
    public void shortestPathDijstra(int start, int[] path, int[] dist) {

    }


    private Edge[] getEdges() {
        Edge[] edges = new Edge[numEdges];
        boolean[][] record = new boolean[numVertexes][numVertexes];
        for (int i = 0; i < record.length; i++) {
            for (int j = 0; j < record[i].length; j++) {
                record[i][j] = false;
            }
        }
        int k = 0;
        for (int i = 0; i < vexs.length; i++) {
            EdgeNode p = vexs[i].getFirstEdge();
            while (p != null) {
                if (!record[i][p.getAdjvexData()]) {
                    edges[k++] = new Edge(i, p.getAdjvexData(), p.getWeight());
                    record[i][p.getAdjvexData()] = true;
                    record[p.getAdjvexData()][i] = true;
                }
                p = p.getNext();
            }
        }
        return edges;
    }

    /**
     * 获取以f节点开始的路径的终点
     *
     * @param parent
     * @param f
     * @return
     */
    private int find(int[] parent, int f) {
        while (parent[f] > 0) {
            f = parent[f];
        }
        return f;
    }

}
